package dynamic;

/**
 * 问题：给定一下长度和对应价格，求如何切割一个长度为n的钢条，使得利益最大<br>
 * <table border = "1"
 * cellPadding="5">
 * <tr>
 * <th>长度</th>
 * <td>1</th>
 * <td>2</th>
 * <td>3</th>
 * <td>4</th>
 * <td>5</th>
 * <td>6</th>
 * <td>7</th>
 * <td>8</th>
 * <td>9</th>
 * <td>10</th>
 * </tr>
 * <tr>
 * <th>价格</th>
 * <td>1</td>
 * <td>5</td>
 * <td>8</td>
 * <td>9</td>
 * <td>10</td>
 * <td>17</td>
 * <td>17</td>
 * <td>20</td>
 * <td>24</td>
 * <td>30</td>
 * </tr>
 * </table>
 *
 * @author longzj
 */
public class CuttingSteal {

    private static final int[] PRICE = {
            1, 5, 8, 9, 10,
            17, 17, 20, 24, 30
    };

    public static void main(String[] args) {
        CuttingSteal steal = new CuttingSteal();
        for (int size = 1; size <= PRICE.length; size++) {
            System.out.println("best price of " + size + " is " + steal.cut(size));
        }
    }

    private int cut(int size) {
        if (size == 0) {
            return 0;
        }
        int[] bestPrice = new int[size];
        return cutInternal(size - 1, bestPrice);
    }

    private int cutInternal(int size, int[] bestPrice) {
        int price = bestPrice[size];
        if (price != 0) {
            return price;
        }
        price = PRICE[size];
        for (int derValue = 1; derValue < size; derValue++) {
            int restSize = size - derValue;
            price = Math.max(price, cutInternal(restSize, bestPrice) + PRICE[derValue - 1]);
        }
        bestPrice[size] = price;
        return price;
    }


}
